// 11-散列4 Hashing - Hard Version

#include "../base/MGraph.c"

/* current ============================================*/
// 图顶点, 用于拓扑排序中的堆，按 value 排序
typedef struct {
    int v; // 顶点编号
    int value; // 顶点的值
} Vertex;

void inputVertex(Vertex vs[], int n) {
    for (int i=0; i<n; i++) {
        scanf("%d", &vs[i].value);
        vs[i].v = i;
    }
}

MGraph* buildGraph(Vertex vs[], int n) {
    MGraph* graph = createGraph(DirectedGraph, MaxWeight, n);
    for (int i=0; i < n; i++) {
        printf("process %d\n", vs[i].value);
        if (vs[i].value < 0) {
            continue;
        }
        // 无冲突位置
        int idx1 = vs[i].value % n;
        if (i == idx1) {
            // 自己和自己不冲突
            continue;
        }
        // 从无冲突位置开始，到当前位置，在图中建立边
        int idx2 = idx1;
        if (idx2 > i) {
            for (; idx2 < n; idx2++) {
                insertEdge(graph, idx2, i, 1);
                printf("insertEdge(%d, %d)\n", vs[idx2].value, vs[i].value);
            }
            idx2 = 0;
        }
        for (; idx2 < i; idx2++) {
            insertEdge(graph, idx2, i, 1);
            printf("insertEdge(%d, %d)\n", vs[idx2].value, vs[i].value);
        }
    }
    return graph;
}

void printVertexs(Vertex vs[], int n) {
    for (int i=0; i<n; i++) {
        if (i != 0) {
            printf(" ");
        }
        printf("%d", vs[i].value);
    }
    printf("\n");
}

int topSort(MGraph* graph, Vertex topOrder[], Vertex vs[]);

int main() {
    int n;
    scanf("%d", &n);
    Vertex* vs = (Vertex*)calloc(n, sizeof(Vertex));
    inputVertex(vs, n);
    MGraph* graph = buildGraph(vs, n);
    printGraph(graph);
    printVertexs(vs, n);

    // 拓扑排序
    Vertex* topOrder = (Vertex*)calloc(n, sizeof(Vertex));
    int outn = topSort(graph, topOrder, vs);
    // 输出
    printVertexs(topOrder, outn);

    // 释放内存
    freeGraph(graph);
    free(vs);
    free(topOrder);
    return 0;
}

// 因为输出时要按值从小到大的顺序输出，所以用最小堆替换原来tuoSort中的队列

#define HeapElementType Vertex*
#include "../base/Heap.c"

int VertexComparator(HeapElementType e1, HeapElementType e2) {
    // 因为默认是最大堆，所以这里要反过来
    return e2->value - e1->value;
}

// 建立，并初始化顶点入度数组
int* initIndegree(MGraph* graph) {
    // 使用 calloc 方法，会把内容初始化为 0
    int* indegree = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 遍历图，得到indegree[] */
    for (int j=0; j < graph->vertexNum; j++) {
        // 第 j 个节点的入度，即与第 j 列连接的边数和
        for (int i=0; i < graph->vertexNum; i++) {
            if (isConnection(graph, i, j)) {
                indegree[j]++;
            }
        }
    }
    return indegree;
}

int topSort(MGraph* graph, Vertex topOrder[], Vertex vs[]) {
    /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int* indegree = initIndegree(graph);

    Heap* heap = createHeap(graph->vertexNum, VertexComparator);
    /* 将所有入度为0的顶点入列 */
    for (int i=0; i < graph->vertexNum; i++) {
        if (indegree[i] == 0 && vs[i].value >= 0) {
            insertHeap(heap, &vs[i]);
        }
    }

    /* 下面进入拓扑排序 */ 
    int cnt = 0; 
    
    while (!isEmptyHeap(heap)) {
        /* 弹出一个入度为0的顶点 */
        Vertex* vertex = deleteHeap(heap); 
        topOrder[cnt++] = *vertex; /* 将之存为结果序列的下一个元素 */
        
        /* 对V的每个邻接点W */
        for (int w=0; w < graph->vertexNum; w++) {
            // 计算 v 的 earliest
            // 这里 w 是 v 的前序节点
            // if (isConnection(graph, w, v)) {
            //     // 有边<w, v>
            //     earliest[v] = max(earliest[v], earliest[w] + graph->g[w][v]);
            // }
            // 这里  w 是 v 的后序节点
            if (isConnection(graph, vertex->v, w)) {
                // 有边<v, w>
                --indegree[w];
                /* 若删除V使得W入度为0 */
                if (indegree[w] == 0) {
                    /* 则该顶点入列 */
                    insertHeap(heap, &vs[w]);
                }
            }
        }
    }
    free(indegree);
    freeHeap(heap);
    return cnt;
}
